1. Field of the Invention
The invention relates to a security system using a Rivest-Shamir-Alderman (RSA) algorithm and a method thereof, and more particularly, to a security system for preventing attacks to Distributed Password Authentication (DPA) by establishing a random coefficient in the execution of the RSA algorithm, and a method thereof.
2. Description of the Related Art
Technology relating to security systems for computers and Internet networks is important with respect to electronic communication, such as e-mail service, electronic trade, and wireless communication. However, to ensure the security of electronic communication, an information safe service, such as a secrecy and a digital signature of a message to be sent, a personal identification, an electronic notarization, and an electronic tender, should be provided.
Current smart cards, which are presently the most secure type of technology, are very susceptible of being hacked. Such hacking of smart cards compromises the security of personal information by the extraction of personal credit information stored in the smart card and the electronic signature generating key, the forgery and the alteration of the certificate of the person himself and the electronic money based on the I.C chip, and other such abuses of personal information. Therefore, a cipher processing of the communication data in the security system of the smart card is necessary. An RSA algorithm is currently recognized as the best public-key cryptography technology.
The RSA (R. L. Rivest, A. Shamir, L. M. Aldmeman) is a cryptography and decipher algorithm using a public key, which the public can know, and a secret key, which a person himself/herself can know, which are utilized in the cryptography that is similar with general public key cryptography.
RSA security is based on that the assumption that the greater a number is the more difficult the factorization of a coprime factor using that number becomes. In other words, a user sending a message designates prime numbers p and q to secret keys and opens the value of n=p*q as the public key to the public. For safety reasons p and q preferably have a length greater than 512 bits, respectively, or a similar length thereto. The user then designates any number e having a relatively prime relationship with a value of Euler quotient function φ(n)=(p−1)(q−1), and opens d satisfying the equation e·d=1 mod φ(n) as the secret key.
When a user1, who wishes to transmit a predetermined message, inputs the predetermined message, a binary number corresponding to the input message is written as a predetermined cryptogram through a binary secret key. This is able to be expressed by an equation C=Md mod N. A user2 then receives the cryptogram and opens the message. The receiver message is able to be expressed by an equation M=Ce mod N. “M” is a variable referring to the message, “d” is a variable referring to the secret key, and “e” and “N” are variables referring to the public keys. The user1 writes a predetermined cryptogram by using the public key and the user2 deciphers the cryptogram by using his/her own secret key.
The exponentiation equation described above is also applied to the electronic signature. Namely, in order to send a digital signature in the message to be sent, a sender sends a signature sentence S and the message M generated through the process S=Md mod n to a receiver, and the receiver certificates the signature as real when the received M and the calculated M′ are identical each other by comparing both M and M′ after decoding through the process M′=Se mod n.
In this cryptography, although the power residue multiplication XY mod N with the cryptography and the decipherment is used, this is able to be reduced to two forms of residue multiplications, A2 mod N and AB mod N. Therefore, when d(i)=0, watching values d(i) of d=d(n), d(n−1) . . . d(0) from the upper most d(n) to the lowest d(0) by one (1) bit sequentially, only A2 mod N is calculated, and when d(i)=1, A2 mod N and AB mod N are calculated. Thus, when d(i)=0, the determination whether i=0 or not is performed after the calculation of A2 mod N, if d(i)=1, then the determination whether i=0 or not is performed after the calculation of A2 mod N and AB mod N, so that two current waveforms corresponding to ei=0 and 1 are represented.
FIGS. 1 and 2 are flowcharts illustrating the RSA algorithm in more detail, more especially illustrating the cryptography using the secret key from the RSA algorithm. FIG. 1 illustrates a method of calculating, as described above, from an upper bit to a lower bit, and FIG. 2 illustrates a method of calculating from the lower bit to the upper bit.
As shown in FIG. 1, when the user1 inputs a message, a binary number M corresponding to the message is inputted as a variable R (operation S11). For example, when a bit number of the secret key d is 1024 bits, since the bit number exists from 0 bit to 1023 bit and the upper most bit (1023rd bit) is ‘1’ as matter of course, the bit number should be started from the next bit. Namely, the bit value of 1022nd corresponding to i=n−2 (operation 12). Here, “i” indicates a bit order of the secret key “d”, and “n” indicates a bit number of the public key N.
Next, the exponentiation for R=R2 mod N is executed by using the value of the initial R (operation 13). In operation 13, it is determined whether the i-th bit value of the secret key d is ‘1’ when the i-th bit value is ‘1’, after the value of M is multiplied to R obtained from R=R2 mod N and divided by N again, the remainder of the calculation is determined as new value of R (operation 15).
When the i-th bit value of d is not ‘1’, then it is again determined whether the calculation is performed to i=0, that is, the lowest bit is determined again (operation 16), and when the value is not ‘0’, the value of i is reduced by one and the exponentiation is executed again (operations 17 and 13). When the lowest bit is determined to be 0 (operation 16), the obtained value of R is determined as the cryptography C (operation 18).
FIG. 2 is a flowchart illustrating the performance of the exponentiation from the lowest bit of the secret key d to the uppermost bit. In comparison with the algorithm shown in FIG. 1, the calculation is performed from i=0 (operation 22) by increasing the value of i-th bit by one (1) bit to the uppermost bit (i=n−1).
In other words, the cryptography M is set to the value of S, and R is set to arbitrary ‘1’ (operation 21), then since the initial value is i=0 (operation 22), whether d(0)=1 or not is determined (operation 23). Namely, if the value of zeroth bit value of the secret key d is zero, the value of R is set to R*S mod N (operation 24), and S is calculated by the exponentiation with an equation S2 mod N (operation 25). If d(0)=0, the value of R is not changed and is directly calculated by the equation S=S2 mod N (operation 25).
After determining whether the value of i is reached to the uppermost bit (operation 26), if not reached, the value of i is increased by ‘1’ (operation 27), the exponentiation is executed again, and if reached to the uppermost bit, the value of R at this time is set to the cryptography (operation 28).
Meanwhile, although the security of the smart card is approved as a safe zone for hacking by the RSA algorithm, the smart card is not approved as a method to challenge a side channel attack that is different from the conventional hacking method.
In general, four types of attacks, such as decap, timing, DPA, and fault insertion, can be included in the side channel attack. The decap is a method of soaking IC chip of the smart card into nitric acid solution in order of finding out circuit drawn on a surface thereof and obtaining principal data by inputting various kind of electric signals into the discovered circuit. The timing attack is a method of finding out the secret key by analyzing the difference between time required for the cryptography algorithm of the IC chip to process information that related to the secret key and time required for the cryptography algorithm to process data that is not related to the secret key. The fault insertion is a method of finding out the secret key in a manner that intentionally inputs wrong information into the IC chip and then analyzes the response data from the IC chip.
The DPA attack is regarded as the most threatening method among the side channel attacks, as well as a method of comparing and analyzing power consumption of the IC chip and when to process data that is related to the secret key and power consumption of the IC chip and when to process data that is not related to the secret key. Namely, the DPA attack originates from the view that the power consumption of CMOS transistor relates to phase transition and hamming weight (number of non-zero bit), therefore the waveform of the power consumption is measured in order to gather statistics while changing the message M by applying an encryption key in the exponentiation (C=Md mod N) of the RSA algorithm. In other words, when the calculation of intermediate result obtained by substituting the value to the RSA algorithm is repeated while changing the encryption key with various values, since a peak with a large current waveform is shown when a correct key is substituted, the secret key is able to be determined by analyzing the waveform of this power consumption and performing a statistical analysis.
Conventionally, to defend against the DPA attack, several methods are used, such as increasing the generation capacity by pairs in order to generate logic data as described in U.S. Pat. No. 6,510,518. In addition, the algorithm is able to be modified to make the prediction for the intermediate data, as described in U.S. Pat. No. 5,991,415.
According to the technology described in U.S. Pat. No. 6,510,518, the hamming weight is modified to have two states, ‘0’ and ‘1’ simultaneously in order, so that the hamming weight is not separated. In this case, the processing burden is increased approximately twice.
According to a method of varying the order of the algorithm and input value by modifying the algorithm proposed in U.S. Pat. No. 6,298,135, since the calculation from the uppermost bit to the lowest bit and the calculation from the lowest bit to the uppermost bit are performed simultaneously or in a mixed state, the calculation speed is lowered, and since the latter half of the calculation is always identical, an attacker is able to predict the algorithm more accurately.
Additional aspects and/or advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.